package leetcode.动态规划.middle;

/**
 * @author wangmaolin1
 * @date 2022/1/16 下午2:06
 */
public class _5最长回文子串 {

    /*
        O(N ²)

     */
    public static String longestPalindrome0(String str) {
        int[][] dp = new int[str.length()][str.length()];
        int start = 0;
        int end = 0;
        int maxLen = 0;
        dp[0][0] = 2;
        for (int i = 0; i < str.length(); i++) {
            for (int j = i; j < str.length(); j++) {
                if (dp[i][j] >= 1) {
                    continue;
                }
                if (j - 1 >= i) {
                    if (dp[i][j - 1] >= 1) {//i-j-1是回文
                        if (dp[i][j - 1] == 1) {
                            dp[i][j] = 0;
                            continue;
                        }
                        dp[i][j] = str.charAt(j) == str.charAt(j - 1) ? 2 : 0;
                        if (dp[i][j] == 2 && j - i > maxLen) { //判断是否为单个字符的回文
                            start = i;
                            end = j;
                            maxLen = j - i;
                        }
                    } else {
                        if ((dp[i][j] = isHuiWen(str, i, j)) >= 1 && (j - i) > maxLen) {
                            start = i;
                            end = j;
                            maxLen = j - i;
                        }
                    }
                }
            }
        }
        return str.substring(start, end + 1);
    }


    /**
     * 动态规划 时间空间都是 O(N²)
     *
     * @param str
     * @return
     */
    public static String longestPalindrome1(String str) {
        if (str.length() < 2) {
            return str;
        }
        boolean[][] dp = new boolean[str.length()][str.length()];
        for (int i = 0; i < str.length(); i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int maxLen = 1;
        for (int len = 2; len < str.length(); len++) {
            for (int i = 0; i < str.length(); i++) {
                int j = len + i - 1;
                if (j >= str.length()) {
                    continue;
                }
                if (str.charAt(j) != str.charAt(i)) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
        return str.substring(start, start + maxLen);
    }

    /**
     * 从中间扩散 本质上是遍历所有回文的中心点，然后从中心点向两边扩散，找到以该点为中心的最长回文的长度
     * <p>
     * 如果是奇数长度，则需要从某个点开始，如12345，则从3开始扩散
     * </p>
     * <p>
     * 如果是偶数长度，则需要从两个点开始，如1234，则从2和3开始扩散
     * </p>
     */
    public static String longestPalindrome2(String str) {
        if (str.length() < 2) {
            return str;
        }
        int start = 0;
        int end = 0;
        for (int i = 0; i < str.length(); i++) {
            int len = spread(str, i, i);
            int len2 = spread(str, i, i + 1);
            int max = Math.max(len2, len);
            if (max > end - start) {
                start = i - (max - 1) / 2;
                end = i + max / 2;
            }
        }
        return str.substring(start, end + 1);
    }

    private static int spread(String str, int i, int j) {
        while (i >= 0 && j < str.length() && str.charAt(i) == str.charAt(j)) {
            i--;
            j++;
        }
        return j - i - 1;
    }

    private static int isHuiWen(String str, int i, int j) {
        if (i == j) {
            return 1;
        }
        boolean same = true;
        char first = str.charAt(i);
        while (i < j) {
            if (str.charAt(i) == str.charAt(j)) {
                i++;
                j--;
                if (str.charAt(i) != first) {
                    same = false;
                }
            } else {
                return 0;
            }
        }
        if (same) {
            return 2;
        }
        return 1;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome1("cbbd"));
    }
}
